package DFS_BFS;

import java.util.Arrays;

/**
 * @PackageName: DFS_BFS
 * @ClassName: LeetCode130
 * @Author: chen jinxu
 * @Date: 2022/3/1 23:10
 * @Description:
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，
 * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 *
 * 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 * 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 *
 * 输入：board = [["X"]]
 * 输出：[["X"]]
 * 
 */
public class LeetCode130 {
    public static void main(String[] args) {
        char[][] board = {{'X','X','X','X'},{'X','0','0','X'},{'X','X','0','X'},{'X','0','X','X'}};
        char[][] solve = solve(board);
        for (char[] chars : solve) {
            System.out.println(Arrays.toString(chars));
        }

    }
    static int n;
    static int m;
    public static char[][] solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return board;
        }
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            // 遍历 每一行第一个元素和最后一个元素
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n -1, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = '0';
                } else if (board[i][j] == '0') {
                    board[i][j] = 'X';
                }
            }
        }
        return board;
    }

    /**
     *
     * @param board 原数组
     * @param x  每一行
     * @param y  每行的边界值
     */
    private static void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != '0') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}
